#include <iostream>
#include <queue>  //用于输出的队列
using namespace std;

//B树节点结构模板
template<class K, size_t M> //K为关键字，M是节点做多包含的关键字数
struct BTreeNode
{
	K _keys[M];  //存储关键字的数组，最多M个
	BTreeNode<K, M>* _subs[M + 1]; //存储子节点指针的数组，最多M+1个
	BTreeNode<K, M>* _parent; //指向父节点指针
	size_t _n;  //当前节点实际包含的关键字数量

    //节点构造函数
	BTreeNode()
	{
        //初始化关键字数组和子节点数组
		for (size_t i = 0; i < M; ++i)
		{
			_keys[i] = K();
			_subs[i] = nullptr;  //子节点指针初始化为空
		}
		_subs[M] = nullptr;  //最后一个子节点指针初始化为空
		_parent = nullptr;
		_n = 0;  //初始化关键字字数为0
	}
};

//B树类模板
template<class K, size_t M>
class BTree
{
	typedef BTreeNode<K, M> Node;  //节点类型别名
public:
    //查找关键在，返回包含关键字的节点和在节点中的索引
    //如果没有找到，最后返回访问的父节点
	pair<Node*, int> Find(const K& key)
	{
		Node* parent = nullptr; //记录父节点
		Node* cur = _root;  //从根节点开始进行查找
		while (cur)  //当前的节点不为空
		{
			size_t i = 0;
			while (i < cur->_n)		// 在当前结点进行查找
			{
				if (key < cur->_keys[i])	// 如果小于则进入与当前下标相同的孩子
				{
					break;  //进入当前索引对应的子节点
				}
				else if (key > cur->_keys[i])	//关键字大于当前位置的关键字
				{
					i++; //继续查找下一个关键字
				}
				else  //找到匹配的关键字
				{
					return make_pair(cur, i);	//返回节点和索引
				}
			}
			parent = cur;  //更新父节点
			cur = cur->_subs[i];  //进入对应子节点继续查找
		}
		return make_pair(parent, -1);	//找不到返回父结点
	}
	
    //在节点中插入关键字和对应的子节点
	void InsertKey(Node* node, const K& key, Node* child)
	{
        //node :要插入关键字的目标节点
        //key :要插入的新关键字
        //child :与新关键字关联的子节点指针
		int end = node->_n - 1;  //从最后一个关键字开始

        //移动关键字和节点，为新关键字腾出一个位置
		while (end >= 0)
		{
			if (key < node->_keys[end]) //将比新关键字大的关键字及其关联的子节点都向后移动一位
			{
				node->_keys[end + 1] = node->_keys[end];
				node->_subs[end + 2] = node->_subs[end + 1];
				--end;
			}
			else
			{
				break;
			}
		}
        //插入新关键字和子节点
		node->_keys[end + 1] = key;
		node->_subs[end + 2] = child;
        //更新父节点指针
		if (child)
		{
			child->_parent = node;
		}
		++node->_n;//更新关键字
	}
	
    //B树的插入操作
	bool Insert(const K& key)
	{
		if (_root == nullptr)	//如果根结点为空，树为空树，此时应该创建一个新的节点作为根节点
		{
			_root = new Node;
			_root->_keys[0] = key;  //将key放入根节点的第一个关键字的位置
			++_root->_n;  //将根节点的关键字数加一
			return true; //返回true表示插入成功
		}
		
        //查找键是否已经存在
		pair<Node*, int> ret = Find(key);	// 借助查找操作来判定是否存在要插入的值
		//Find函数返回一个pair，其中第一个元素是找到的节点指针，第二元素是键在节点的索引
        if (ret.second >= 0)				// 如果不存在则可以找到要进行插入的位置
		{
			return false;
		}

        //初始化插入所需的变量
		Node* parent = ret.first; //获取要插入的父节点
		K newKey = key;  //要插入的关键字
		Node* child = nullptr;  //要插入的子节点（初始为空）

        //循环插入和处理节点分裂
		while (1)
		{
			InsertKey(parent, newKey, child);	//插入关键字到父节点
			if (parent->_n < M)					//节点关键字数量未达到上限，插入成功
			{
				return true;
			}
			else						//关键字达到上限，需要分裂
			{
				size_t mid = M / 2;  //中间位置为分裂点
				Node* brother = new Node;  //创建新的兄弟节点

                //将中间位置右侧的关键字和子节点移动到兄弟节点
				size_t i = mid + 1;
				size_t j = 0;
				for (; i < M; ++i)		
				{
					brother->_keys[j] = parent->_keys[i];
					brother->_subs[j] = parent->_subs[i];

                    //如果子节点存在，更新其父节点指针
					if (parent->_subs[i])
					{
						parent->_subs[i]->_parent = brother;
					}
					++j;

					// 清空父节点已经移走的关键字和子节点
					parent->_keys[i] = K();
					parent->_subs[i] = nullptr;
				}
                //移动最后一个子节点
				brother->_subs[j] = parent->_subs[i];

				if (parent->_subs[i])
				{
					parent->_subs[i]->_parent = brother;
				}
				parent->_subs[i] = nullptr;

                //更新节点关键字的数量
				brother->_n = j;
				parent->_n -= (brother->_n + 1);  //减去已经移走的关键字和中间关键字

                //中间关键字将上升到父节点
				K midKey = parent->_keys[mid];
				parent->_keys[mid] = K();  //清空中间关键字

				if (parent->_parent == nullptr)	// 如果没有父结点，则新建
				{
                    //创建新的根节点
					_root = new Node;  
					_root->_keys[0] = midKey; //中间关键字成为新的根节点
					_root->_subs[0] = parent; //原来父节点成为新根的左子节点
					_root->_subs[1] = brother; //兄弟节点成为新根节点的右子节点
					_root->_n = 1; //新根关键字数为1
					parent->_parent = _root;  //设置父节点的父指针
					brother->_parent = _root;  //设置兄弟节点的父指针
					break;  //分裂完成
				}
				else	//父节点不是根节点
				{
                    //准备向上层插入中间关键字
					newKey = midKey;
					child = brother;
					parent = parent->_parent;  //移动到上层
				}
			}
		}
		return true;
	}
	
	// 中序遍历
	void _InOrder(Node* cur)
	{
		if (cur == nullptr)
			return;

		// 左 根  左 根  ...  右
		size_t i = 0;
		for (; i < cur->_n; ++i)
		{
			_InOrder(cur->_subs[i]); // 左子树
			cout << cur->_keys[i] << " "; // 根
		}

		_InOrder(cur->_subs[i]); // 最后的那个右子树
	}

    //中序遍历接口
	void InOrder()
	{
		_InOrder(_root);
	}
	
	// 按层输出B树
	void PrintByLevel()
	{
		if (_root == nullptr)
		{
			cout << "B树为空" << endl;
			return;
		}
		
		queue<Node*> q;  //用于层次遍历的队列
		q.push(_root);  //根节点进入队列
		int level = 0;  //当前层数
		
		while (!q.empty())
		{
			size_t levelSize = q.size();
			cout << "Level " << level << ": ";
			
			for (size_t i = 0; i < levelSize; ++i)
			{
				Node* cur = q.front(); //获取队首节点
				q.pop();  //队首节点出队
				
				// 输出当前节点的所有关键字
				for (size_t j = 0; j < cur->_n; ++j)
				{
					cout << cur->_keys[j] << " ";
				}
				
				// 将子节点加入队列
				for (size_t j = 0; j <= cur->_n; ++j)
				{
					if (cur->_subs[j] != nullptr)
					{
						q.push(cur->_subs[j]);
					}
				}
			}
			
			cout << endl;  //当前层输出结束
			level++;//层数加一
		}
	}

private:
	Node* _root = nullptr;
};

int main()
{
	int a[] = { 53, 139, 75, 49, 145, 36, 101 };
	BTree<int, 3> t;
	for (auto e : a)
	{
		t.Insert(e);
	}
	
	cout << "中序遍历: ";
	t.InOrder();
	cout << endl << endl;
	
	cout << "按层输出B树:" << endl;
	t.PrintByLevel();
	
	return 0;
}
    